/**
 * Consider the fraction, p/q, where p and q are positive integers. If p < q 
 * and gcd(p,q)=1, it is called a reduced proper fraction.
 *
 * If we list the set of reduced proper fractions for q <= 8 in ascending order
 * of value, we get:
 *
 *   1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 
 *   5/7, 3/4, 4/5, 5/6, 6/7, 7/8
 *
 * It can be seen that 2/5 is the fraction immediately to the left of 3/7.
 *
 * By listing the set of reduced proper fractions for q <= 1,000,000 in 
 * ascending order of size, find the numerator of the fraction immediately 
 * to the left of 3/7.
 *
 * ANSWER: 428570.
 */

#include <iostream>
#include "farey.h"

void solve_problem_71()
{
	const int M = 1000000;
	const int a = 3, b = 7;

#if 1
	farey_sequence_iterator<int> it = --farey_sequence<int>(M).find(a, b);
	std::cout << it->numerator() << std::endl;
#else
	std::pair<int,int> best_frac(0, 1);
	std::pair<int,int> best_distance(a, b);
	for (int q = 2; q <= M; q++)
	{
		int p = (a*q - 1) / b;
		std::pair<int,int> d(a*q-b*p, b*q);
		if (d.first * best_distance.second < d.second * best_distance.first)
		{
			best_frac = std::pair<int,int>(p, q);
			best_distance = d;
		}
	}

	std::cout << best_frac.first << std::endl;
#endif
}
